// 1.有重复值，第一个等于target的值
function binary_change01(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (arr[mid] < target) {
            low = mid + 1
        } else if (arr[mid] > target) {
            high = mid - 1
        } else {
            if (mid === 0 || arr[mid - 1] !== target) return mid
            else high = mid - 1
        }
    }
    return -1
}

// 2.有重复值，最后一个等于target的值
function binary_change02(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (arr[mid] < target) {
            low = mid + 1
        } else if (arr[mid] > target) {
            high = mid - 1
        } else {
            if (mid === high || arr[mid + 1] !== target) return mid
            else low = mid + 1
        }
    }
    return -1
}

// 3.无重复值，第一个大于target的值
function binary_change03(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (arr[mid] < target) {
            low = mid + 1
        } else {
            if (mid === 0 || arr[mid - 1] < target) return mid
            else high = mid - 1
        }
    }
    return -1
}

// 4.无重复值最后一个小于等于target的值
function binary_change04(arr, target) {
    let low = 0
    let high = arr.length - 1
    while (low <= high) {
        let mid = Math.floor((low + high) / 2)
        if (arr[mid] > target) {
            high = mid - 1
        } else {
            if (mid === high || arr[mid + 1] > target) return mid
            else low = mid + 1
        }
    }
}


let array = [2, 3, 22, 22, 22, 29, 35, 67]
let index = binary_change01(array, 22)
console.log(index)
index = binary_change02(array, 22)
console.log(index)
array = [2, 3, 8, 9, 21, 29, 35, 67]
index = binary_change03(array, 22)
console.log(index)
index = binary_change04(array, 22)
console.log(index)